package linkedlist.leetcode_138;

public class Solution2 {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        //将拷贝节点插入到原节点后面
        Node copyNode = null;
        Node cur = head;
        while(cur != null){
            Node temp = cur.next;
            copyNode = new Node(cur.val);
            cur.next = copyNode;
            copyNode.next = temp;
            cur = temp;
        }

        cur = head;
        //设置拷贝节点的随机节点
        while(cur != null){
            Node temp = cur.next.next;
            copyNode = cur.next;
            copyNode.random = cur.random == null ? null : cur.random.next;
            cur = temp;
        }
        //此时，原链表的head.next就是拷贝后链表的head
        Node res = head.next;

        //将链表拆分
        //7(cur) --> 7'(copyNode = cur.next) --> 13(nextNode = cur.next.next) --> 13'
        //7 --> 13
        //7'(copyNode) --> 13'(nextNode.next)
        cur = head;
        while(cur != null){
            Node temp = cur.next.next;
            copyNode = cur.next;
            copyNode.next = temp == null ? null : temp.next;
            cur.next = temp;
            cur = temp;
        }
        return res;
    }
}
